package LeetCode;

import java.util.LinkedList;
import java.util.Queue;

public class LC_513_FindBottomLeftTreeValue {

    public static void main(String[] args) {

    }

    static class Solution {
        int ret = 0;

        public int findBottomLeftValue(TreeNode root) {
            if (root == null) return ret;
            bfs(root);
            return ret;
        }

        private void bfs(TreeNode root) {
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            ret = root.val;
            int curNum = 1;
            int nextNum = 0;
            while (!q.isEmpty()) {
                TreeNode node = q.poll();
                curNum--;
                if (node.left != null) {
                    q.offer(node.left);
                    nextNum++;
                }
                if (node.right != null) {
                    q.offer(node.right);
                    nextNum++;
                }
                if (curNum == 0) {
                    if (!q.isEmpty()) ret = q.peek().val;
                    curNum = nextNum;
                    nextNum = 0;
                }
            }
        }

    }

    public class Solution_2 {
        public int findBottomLeftValue(TreeNode root) {
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            while (!q.isEmpty()) {
                root = q.poll();
                if (root.right != null)
                    q.add(root.right);
                if (root.left != null)
                    q.add(root.left);
            }
            return root.val;
        }

    }

    static class Solution_3 {
        public class Solution {
            int ans = 0, pre = 0;

            public int findBottomLeftValue(TreeNode root) {
                findBottomLeftValue(root, 1);
                return ans;
            }

            void findBottomLeftValue(TreeNode root, int depth) {
                if (pre < depth) {
                    ans = root.val;
                    pre = depth;
                }
                if (root.left != null)
                    findBottomLeftValue(root.left, depth + 1);
                if (root.right != null)
                    findBottomLeftValue(root.right, depth + 1);
            }
        }
    }

    static class Solution_4 {
        public class Solution {
            public int findBottomLeftValue(TreeNode root) {
                return findBottomLeftValue(root, 1, new int[]{0, 0});
            }

            int findBottomLeftValue(TreeNode root, int depth, int[] res) {
                if (res[1] < depth) {
                    res[0] = root.val;
                    res[1] = depth;
                }
                if (root.left != null)
                    findBottomLeftValue(root.left, depth + 1, res);
                if (root.right != null)
                    findBottomLeftValue(root.right, depth + 1, res);
                return res[0];
            }
        }
    }


}